package 二叉搜索树的最近公共祖先;

/**
 * @author AirMan
 * @version 1.0
 * @description 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
 * 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
 * 例如，给定如下二叉搜索树:  root = [6,2,8,0,4,7,9,null,null,3,5]
 * @date 2025/4/7 9:38
 */
public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 递归法
        // 递归的参数：TreeNode root, TreeNode p, TreeNode q
        // 递归返回值：TreeNode
        // 递归的终止条件：root == null，因为本题限制了p、q 为不同节点且均存在于给定的二叉搜索树中，终止条件可以不需要
        // 单层递归逻辑：只需要找到root的值介于两节点之间，并且root是第一次符合该条件的节点。不需要处理中间节点的逻辑
        // 所以随便采用遍历方法，如果遍历的当前节点值比两节点的区间值都要小，那么往right遍历。如果遍历的当前节点值比
        // 两节点的区间值都要大，那么往left遍历。只要出现当前的节点值位于两节点的区间范围，那么就返回当前节点

        if (p.val > q.val) {
            TreeNode temp = p;
            p = q;
            q = temp;
        }
        if (root == null)
            return root;
        /*
        if (root.val >= p.val && root.val <= q.val) {
            // 只要出现当前的节点值位于两节点的区间范围，那么就返回当前节点
            return root;
        } else if (root.val > q.val) {
            // 如果遍历的当前节点值比两节点的区间值都要大，那么往left遍历
            return lowestCommonAncestor(root.left, p, q);
        } else {
            // 如果遍历的当前节点值比两节点的区间值都要小，那么往right遍历
            return lowestCommonAncestor(root.right, p, q);
        }
         */
        if (root.val > q.val) {
            // 如果遍历的当前节点值比两节点的区间值都要大，那么往left遍历
            return lowestCommonAncestor(root.left, p, q);
        } else if (root.val < p.val) {
            // 如果遍历的当前节点值比两节点的区间值都要小，那么往right遍历
            return lowestCommonAncestor(root.right, p, q);
        }else {
            // 如果跳过前两步if能走到这一步，就说明第一次出现了root.val >= p.val && root.val <= q.val
            // 只要出现当前的节点值位于两节点的区间范围，那么就返回当前节点
            return root;
        }
    }
}
